#include<stdio.h>
#include<stdlib.h>
#define INIT 5
#define INCR 3
#define N 8
#define E 7
int matrix[N+1][N+1];

typedef struct{
	int *base;
	int *top;
	int size;
}stack;

void Init_Stack(stack *sp){
	sp->base=(int *)malloc(INIT*sizeof(int));
	sp->top=sp->base;
	sp->size=INIT;
}

void Push_Stack(stack *sp,int e){
	if(sp->top-sp->base>=sp->size){
		sp->base=(int *)realloc(sp->base,(sp->size+INCR)*sizeof(int));
		sp->top=sp->base+sp->size;
		sp->size=sp->size+INCR;
	}
	*(sp->top)=e;
	sp->top++;
}	

int Pop_Stack(stack *sp){
	sp->top--;
	return *(sp->top);
}

int Empty_Stack(stack s){
	if(s.top==s.base)
		return 1;
	else
		return 0;
}

typedef struct qnode{
	int data;
	struct qnode *next;
}qnode;

typedef struct{
	qnode *front;
	qnode *rear;
}queue;

void Init_Queue(queue *qp){
	qp->front=(qnode *)malloc(sizeof(qnode));

	(qp->front)->data=0;
	(qp->front)->next=NULL;

	qp->rear=qp->front;
}

void Push_Queue(queue *qp,int e){
	qnode *s=(qnode *)malloc(sizeof(qnode));

	s->data=e;
	s->next=NULL;

	(qp->rear)->next=s;
	qp->rear=s;
}

int Pop_Queue(queue *qp){
	qnode *s=qp->front->next;
	int tmp=s->data;
	qp->front->next=s->next;
	if(qp->rear==s)
		qp->rear=qp->front;
	free(s);
	return tmp;
}

int Empty_Queue(queue q){
	if(q.rear==q.front)
		return 1;
	else 
		return 0;
}
void Matrix(){
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			matrix[i][j]=0;
	FILE *fp;
	fp=fopen("test.txt","r");
	int e=E;
	int a,b;
	while(e--){
		fscanf(fp,"%d%d",&a,&b);
		matrix[a][b]=1;
		matrix[b][a]=1;
	}
}

void DFS(int start){
	printf("DFS:\n");
	stack s;
	int tmp;
	int mark[N+1]={0};
	Init_Stack(&s);
	Push_Stack(&s,start);
	mark[start]=1;
	while(!Empty_Stack(s)){
		tmp=Pop_Stack(&s);
		printf("%d\t",tmp);
		for(int i=1;i<=N;i++){
			if(mark[i]==0 && matrix[tmp][i]==1){
				Push_Stack(&s,i);
				mark[i]=1;
			}
		}
	}
	printf("\n");
}

void BFS(int start){
	printf("BFS:\n");
	queue q;
	int tmp;
	int mark[N+1]={0};
	Init_Queue(&q);
	Push_Queue(&q,start);
	mark[start]=1;
	while(!Empty_Queue(q)){
		tmp=Pop_Queue(&q);
		printf("%d\t",tmp);
		for(int i=1;i<=N;i++){
			if(mark[i]==0 && matrix[tmp][i]==1){
				Push_Queue(&q,i);
				mark[i]=1;
			}
		}
	}
	printf("\n");
}

int main(){
	Matrix();
	DFS(1);
	BFS(1);
	return 0;
}